package exams.array;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collector;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class SortSolution {

    public void sort(int[][] input) {
        quickSort(input, 0, input.length - 1);
    }

    public void quickSort(int[][] input, int low, int high) {
        if(low < high) {
            int pv = partition(input, low, high);
            quickSort(input, low, pv - 1);
            quickSort(input, pv + 1, high);
        }
    }

    private int partition(int[][] input, int low, int high) {
        int[] pe = input[low];
        while (low < high) {
            while (low < high && compare(input[high], pe) <= 0) {
                high --;
            }
            input[low] = input[high];
            while (low < high && compare(input[low], pe) >=0 ) {
                low ++;
            }
            input[high] = input[low];
        }

        input[low] = pe;
        return low;
    }

    private int compare(int[] a, int[] b) {
        return a[0] * b[1] - b[0] * a[1];
    }

    // ["John Kyen", "Tom Sim"] 排序， 1. 按 last name 中重复字母最多的字母数排序， 2.按last name ，自然顺序排， 3. 按 first name 自然顺序排
    public String[] sort(String[] args) {
      List<String> res = Arrays.asList(args);
      res.sort((String str1, String str2) -> {
          String[] arr1 = str1.split(" ");
          String fN1 = arr1[0];
          String lN1 = arr1[1];
          String[] arr2 = str2.split(" ");
          String fN2 = arr2[0];
          String lN2 = arr2[1];
          long c1 = count(lN1);
          long c2 = count(lN2);
          if(c1 == c2) {
             if(lN1.equals(lN2)) {
                 return fN1.compareTo(fN2);
             }
             return lN1.compareTo(lN2);
          }
          return Long.compare(c1, c2);
      });

      return res.toArray(new String[res.size()]);
    }

    public long count(String str) {
        Map<Character, Long> map = str.chars()
                .mapToObj(o -> (char) o)
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        return map.entrySet().stream().max(Map.Entry.comparingByValue()).orElse(null).getValue();
    }

    // ["John Kyen", "Tom Sim"] 排序， 1. 按 last name 中重复字母最多的字母数排序， 2.按last name ，自然顺序排， 3. 按 first name 自然顺序排
    public String[] sort2(String[] args) {
        Map<String, Long> map = Arrays.asList(args).stream().collect(Collectors.toMap(Function.identity(), o -> this.count(o.split(" ")[0])));

        Arrays.sort(args, (o1, o2) -> {
            String[] arr1 = o1.split(" ");
            String fN1 = arr1[0];
            String lN1 = arr1[1];
            String[] arr2 = o2.split(" ");
            String fN2 = arr2[0];
            String lN2 = arr2[1];
            long c1 = map.get(o1);
            long c2 = map.get(o2);

            if(c1 == c2) {
                if(lN1.equals(lN2)) {
                    return fN1.compareTo(fN2);
                }
                return lN1.compareTo(lN2);
            }

            return Long.compare(c1, c2);
        });

        return args;
    }


    // array couples
    // [1,4,2,3,3,2] (k, k+1), (k+2, k+3) 中没有对称的对是1,4  [1,2,2,1] 不存在没有对称对的话返回“yes”
    public static String checkSymmetricPairs(int[] arr) {
        List<Integer> list = Arrays.stream(arr).boxed().toList();
        List<Integer> revList = Arrays.stream(arr).boxed().toList().reversed();

        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<revList.size(); i += 2) {
            String key = revList.get(i) + "," + revList.get(i+1);
            if(!map.containsKey(key)) {
                map.put(key, 0);
            }
            map.put(key, map.get(key) + 1);
        }
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<list.size(); i +=2) {
            String t = list.get(i) + "," + list.get(i+1);
            if(!map.containsKey(t)) {
                res.add(list.get(i));
                res.add(list.get(i+1));
            } else {
                if(list.get(i).equals(list.get(i+1)) && map.get(t) < 2) {
                    res.add(list.get(i));
                    res.add(list.get(i+1));
                }
            }
        }
        if(res.isEmpty()) {
            return "yes";
        }

        return res.stream().map(String::valueOf).collect(Collectors.joining(","));
    }

}
